# -*- coding: utf-8 -*-
"""剑指 Offer 07. 重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

示例 2:
Input: preorder = [-1], inorder = [-1]
Output: [-1]

限制：
0 <= 节点个数 <= 5000
"""

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    """遍历二叉树的特征：
    前序遍历，其根节点是遍历的第一个结果
    中序遍历，左子树的遍历结果在根节点左侧，右子树的遍历结果在根节点右侧
    
    那么给一个二叉树的前序遍历和中序遍历结果，可以确定该树的顶点，左子树，右子树
    然后左子树又可以从前序遍历的全结果中找出该子树顶点（子树这些节点谁在前序遍历结果中是第一个），找到顶点就可以分出左右子树，如此递归
    右子树亦然"""
    def buildTree(self, preorder: list, inorder: list) -> TreeNode:
        if not preorder:
            return

        vertexs = {}
        i = 0
        for v in preorder:
            vertexs[v] = i
            i += 1

        def do(head, tail):
            if head == tail:
                return TreeNode(inorder[head])

            vertex, idx = None, None

            minvertexidx = float('+inf')
            point = head
            while point <= tail:
                curridx = vertexs[inorder[point]]
                if curridx < minvertexidx:
                    minvertexidx = curridx
                    vertex = inorder[point]
                    idx = point
                point += 1

            left = do(head, idx-1) if head <= idx-1 else None
            right = do(idx+1, tail) if tail >= idx+1 else None

            treeNode = TreeNode(vertex)
            treeNode.left = left
            treeNode.right = right

            return treeNode

        return do(0, len(inorder)-1)


if __name__ == '__main__':
    preorder = [3,9,20,15,7]
    inorder = [9,3,15,20,7]
    rs = Solution().buildTree(preorder, inorder)
    print(rs)
